perm filename WORDAL[1,RWF] blob
sn#728160 filedate 1983-09-21 generic text, type C, neo UTF8
COMMENT ā VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 Reliable Algorithms
C00011 00003 An algorithm need not work with numbers. Here is an algorithm to find a word in
C00016 ENDMK
Cā;
Reliable Algorithms
Robert W. Floyd
Copyright 1983
There is a traditional algorithm used by Russian peasants to multiply numbers
of several digits, based on doubling, halving, and addition. To see why it
works, let's first look at a particular multiplication problem.
How much is 38 x 45? Since 38 = 19 x 2, 38 x 45 = 19 x 2 x 45 = 19 x 90.
That's 90 more than 18 x 90, so
19 x 90 = 18 x 90 + 90 = 9 x 2 x 90 + 90 = 9 x 180 + 90
Since 9 x 180 is 180 more than 8 x 180,
9 x 180 + 90 = 8 x 180 + 180 + 90 = 8 x 180 + 270
= 4 x 2 x 180 + 270 = 4 x 360 + 270
4 x 360 + 270 = 2 x 2 x 360 + 270 = 2 x 720 + 270 = 1440 + 270 = 1710.
Now that the method is clear, the process can be shortened to filling out a table.
In each row, we have two numbers we want to multiply, and another number to be
added on to the result. For the calculation above, here is the table:
A B C
38 45 0
19 90 0
18 90 90
9 180 90
8 180 270
4 360 270
2 720 270
1 1440 270
0 1440 1710
Here is an explicit algorithm for making the table.
(1) The first row across contains, in columns A and B, the numbers we want to
multiply, 38 and 45 in this example, and in column C a zero.
(2) If A=0 in the bottom row of the table, we are finished; the entry in column C
is the answer. Otherwise we need to make another row.
(3) If A is even in the bottom row, we make the next row by halving the number
in column A, doubling the number in column B, and copying the previous number
from column C.
(4) If A is odd in the bottom row, we make the next row by subtracting one from
the number is column A, copying the member in column B, and adding the number
from column B to the number in column C.
Every row in the table stands for a formula; the fifth row, above, stands for
8 x 180 + 270. People who work with algorithms find ways to represent entities
that are not just numbers by sequences of numbers; this allows using computers
that only handle numbers to solve problems that involve not only numbers, but
pictures, words, formulas, logic, and myriad others.
The successive rows represent different formulas, but each formula stands for
the same number as the one before it, so they all stand for the same number.
We get from the problem to the solution by picking a first line that is easy
to construct from the problem, and getting to a last line from which it is easy
to construct the solution. In between, we need steps that are easy to carry
out, that progress toward an acceptable last line, and that change the question
without changing the answer. That is, we go from ``What is 8 x 180 + 270?'' to
``What is 4 x 360 + 270?'' without changing the answer, 1710.
A good algorithm is like good government; it involves both stability and progress.
Progress in solving a problem comes from changing it into a simpler problem;
stability comes from assuring that each new problem has the same answer as the one
it grew from. In the Russian peasant multiplication algorithm, progress is
quaranteed because columnn A gets closer to zero at every step; it can't go on
forever, since there are only a limited number of possible values A can have,
once we know the first value. Stability is guaranteed because in each row, the
formula AxB+C has the same value.
A similar algorithm, known to Euclid around 430 B.C., finds the largest number
that evenly divides two given numbers. If we want to reduce a fraction like
385/315 to its simplest form, we find 35 as the greatest common divisor (g.c.d.)
of 385 and 315, and say 385/315 = (385/35)/(315/35) = 11/9. We can get greatest
common divisors by trial and error, but there is a much more efficient way.
Here is a table given by Euclid's algorithm finding the g.c.d. of 385 and 3l5:
A B
315 385
315 70
70 315
70 245
70 175
70 35
35 70
35 35
The algorithm sets up the first row with the smaller number in column A, and
the larger in column B. As long as B is bigger than A, it makes the next row
by copying A, and reducing B by A (subtraction). If B gets smaller than A, it
makes the next row by exchanging A with B. If B is equal to A in a row, that
number is the greatest common divisor.
The principle of stability is that the common divisors of A and B are the same
in each row. In this example, in every row both A and B are multiples of
1,5,7, and 35. If we decrease B by A, the result is still a multiple of
1,5,7, and 35, but no new common divisors are introduced (a little easy algebra
will convince you).
The principle of progress can be formulated in several ways. One way is that
the value of 2A+B decreases at every step, while staying positive.
A more efficient formulation of Euclid's algorithm uses remainders (of division)
rather than subtraction. Here it finds the g.c.d. of 315 and 385 again:
A B
315 385
70 315
35 70
0 35
As before, in the first line A is the smaller datum, B the larger. When we get
to a line with A=0, we stop, and B is the answer. Otherwie, we find the
remainder when B is divided by A. In the next line, A is that remainder, while
B is copied from A in this line.
In the improved version of the algorithm, the principle of stability is the same;
all the rows have the same common divisors and therefore the same g.c.d. The
principle of progress is that A decreases at every step, without becoming negative.
An algorithm need not work with numbers. Here is an algorithm to find a word in
the dictionary.
Insert your left index finger between pages at the beginning of the dictionary,
and your right index finger at the end. Open the dictionary somewhere between
your fingers (If you can't, you've already found the right page). Look at the
word in the top left corner of the newly opened page. If it is alphabetically
earlier than the word you are looking for, move your left index finger into the
new opening; otherwise, move your right index finger there. Here is a record of
my looking up ``scutage'' in the Shorter Oxford English Dictionary.
Left finger Right finger New opening
page number word page number word page number word
1 A 2475 Zygin 1278 Monthly
1278 Monthly 2475 Zygin 1822 Sea-horse
1278 Monthly 1822 Sea-horse 1542 Pomatum
1542 Pomatum 1822 Sea-horse 1682 Redowa
1682 Redowa l822 Sea-horse 1730 Revolutionary
1730 Revolutionary 1822 Sea-horse 1780 Sailyard
1780 Sailyard 1822 Sea-horse 1800 Scantity
1800 Scantity 1822 Sea-horse 1810 Scorer
1810 Scorer 1822 Sea-horse 1816 Scriptural
1816 Scriptural 1822 Sea-horse 1820 Sea
1816 Sciptural 1822 Sea-horse 1818 Sculptile
1818 Sculptile 1820 Sea (none)
The principle of stability is that the word I'm looking for stays between my
fingers. The principle of progress is that the number of pages between my
fingers gets smaller.
Many algorithms embodied in computer programs are not reliable; when used on
certain data they give wrong answers, or they continue calculating until
someone intervenes. The way to make an algorithm reliable is to design it
around a principle of stability and a principle of progress. If you can't
formulate a principle of stability for an algorithm, it is likely to change
the problem it is solving as it goes along, and end up computing the right
answer to the wrong problem. If you can't formulate a principle of progress,
the algorithm is likely to run forever on some data. As the Russian peasant
multiplication and greatest common divisor algorithms show, it becomes much
easier to understand a new algorithm when its principle of stability (technically
known as an invariant) is presented with it.